package com.xgh.sortMethods;

import java.util.Arrays;
import java.util.stream.Stream;

/**
 * @ClassName JavaSort
 * @Description
 * @Author xinggh
 * @Date 2020/6/17 15:28
 * @Version 1.0
 **/
public class JavaSort {

    /**
     * 二分查询
     *
     * @param arr
     * @param target
     * @return
     */
    public static int biSearch(int arr[], int target) {
        int start = 0;
        int end = arr.length - 1;

        while (start <= end) {
            int mid = (start + end) / 2;
            if (arr[mid] == target) {
                return mid;
            } else if (arr[mid] < target) {
                start = mid + 1;
            } else if (arr[mid] > target) {
                end = mid - 1;
            }
        }
        return -1;
    }


    /**
     * 冒泡排序1
     *
     * @param arr
     * @return
     */
    public static void bubbleSort1(int arr[]) {
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr.length - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    int tmp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = tmp;
                }
            }
        }
        System.out.println(1);
    }

    /**
     * 快速排序 平均时间复杂度o(nLogn)
     *
     * @param arr
     * @param low
     * @param hight
     */
    public static void quickSort(int arr[], int low, int hight) {
        if (low < hight) {
            int key = arr[low];
            int i = low;
            int j = hight;

            while (i < j) {
                //从后边开始移动
                while (i < j && arr[j] >= key) {
                    j--;
                }
                if (arr[j] < key) {
                    int tmp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = tmp;
                    i++;
                }
                while (i < j && arr[i] <= key) {
                    i++;
                }
                if (arr[i] > key) {
                    int tmp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = tmp;
                    j--;
                }
            }
            arr[i] = key;
            quickSort(arr, low, i - 1);
            quickSort(arr, i + 1, hight);
        }
    }

    /**
     * 插入排序
     * 将一个记录插入到已经拍好序的序列中，从而得到一个新的序列
     *
     * @param arr
     */
    public static void insertSort(int arr[]) {

        for (int i = 1; i < arr.length; i++) {
            int insertValue = arr[i];
            int index = i - 1;
            while (index > 0 && insertValue < arr[index]) {
                arr[index + 1] = arr[index];
                index--;
            }

            arr[index + 1] = insertValue;

        }
    }


    public static void printf(int arr[]) {
        System.out.println(Arrays.toString(arr));

    }

    /**
     * 输出在数组中第一个大于等于查找值的位置，如果数组中不存在这样的数，则输出数组长度加一。
     *
     * @return
     */
    public static int binarySearchOne() {
        int[] array = {1, 3, 3, 3, 5, 6};
        int target = 3;
        int left = 0, right = array.length - 1;
        while (left <= right) {
            //只修改了判断的条件，相当于将小于等于归为一类。
            int mid = (left + right) / 2;
            if (array[mid] >= target) {
                if (mid == 0 || array[mid - 1] < target) {
                    return mid + 1;
                } else {
                    right = mid;
                }
            } else {

                left = mid + 1;
            }

        }
        return left;
    }

    public static void main(String[] args) {
        //int arr[] = {1, 1, 3, 4, 5, 6};
        int arr[] = {3, 4, 1, 5, 2};
        //int arr[] = {72, 6, 57, 88, 60, 42};
        // int tar = 2;
        //System.out.println(biSearch(arr, tar));
      /*  quickSort(arr, 0, arr.length - 1);
        printf(arr);
        insertSort(arr);
        printf(arr);*/
        System.out.println(binarySearchOne());
        String s1 = "hello";
        String s2 = "world";
        String s3 = "hello" +"world";
        String s4 = s1 + "world";
        String s5 = "hello" + s2;
        System.out.println(s4==s5);

    }
}
